// 递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
// 1.如果需要搜索整颗二叉树且不用处理递归返回值，递归函数就不要返回值。
// （113.路径总和ii）
// 2. 如果需要搜索整颗二叉树且需要处理递归返回值，递归函数就需要返回值。
// （236. 二叉树的最近公共祖先)
// 3.如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，
// 因为遇到符合条件的路径了就要及时返回。（112.路径总和）

class Solution {
 public:
  // 本题前中后序遍历都行，因为中节点也没有处理逻辑
  bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (hasPathSum(root->left, targetSum - root->val)) return true;
    if (!root->left && !root->right && targetSum == root->val) return true;
    if (hasPathSum(root->right, targetSum - root->val)) return true;
    return false;
  }
  // 先序遍历，迭代写法
  bool haspathsum(treenode* root, int sum) {
    if (root == nullptr) return false;
    // 此时栈里要放的是pair<节点指针，路径数值>
    stack<pair<treenode*, int>> st;
    st.push(pair<treenode*, int>(root, root->val));
    while (!st.empty()) {
      pair<treenode*, int> node = st.top();
      st.pop();
      // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
      if (!node.first->left && !node.first->right && sum == node.second)
        return true;

      // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
      if (node.first->right) {
        st.push(pair<treenode*, int>(node.first->right,
                                     node.second + node.first->right->val));
      }

      // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
      if (node.first->left) {
        st.push(pair<treenode*, int>(node.first->left,
                                     node.second + node.first->left->val));
      }
    }
    return false;
  }
};